from typing import *


class Solution:

    def pondSizes(self, land: List[List[int]]) -> List[int]:

        class UnionFind():

            def __init__(self, size: int) -> None:
                self.p = [i for i in range(size)]
                self.cnts = [1] * size
                self.size = size

            def find(self, a):
                if self.p[a] != a:
                    self.p[a] = self.find(self.p[a])
                return self.p[a]

            def union(self, a: int, b: int):
                A, B = self.find(a), self.find(b)
                if A != B:
                    self.p[B] = A
                    self.cnts[A] += self.cnts[B]
                    self.cnts[B] = 0
                    self.size -= 1

            def isSameSet(self, a: int, b: int) -> bool:
                return self.find(a) == self.find(b)

        d8 = [(-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1),
              (0, -1)]

        array = land
        m, n = len(array), len(array[0])
        uf = UnionFind(m * n)
        for i in range(m):
            for j in range(n):
                for x, y in d8:
                    nx, ny = i + x, j + y
                    if nx >= 0 and nx < m and ny >= 0 and ny < n:
                        if (array[i][j] == 0 and array[nx][ny] == 0) or (
                                array[i][j] != 0 and array[nx][ny] != 0):
                            uf.union(i * n + j, nx * n + ny)

        d = dict()
        for i in range(m):
            for j in range(n):
                if array[i][j] == 0:
                    d[uf.find(i * n + j)] = uf.cnts[uf.find(i * n + j)]
        return sorted([v for k, v in d.items()])


so = Solution()
print(so.pondSizes([[0, 2, 1, 0], [0, 1, 0, 1], [1, 1, 0, 1], [0, 1, 0, 1]]))
